/*
 * Copyright 北京航空航天大学  @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.dp;

/**
 * <p>
 * 迷宫路径总数目 
 * 给定一个m*n的矩阵，从左上角到右下角的路径数，只能向右、向下移动
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com
 * @time 2015年5月30日
 */
public class UniquePaths {
    //二维降一维
public int uniquePaths(int m, int n) {
     int dp [] = new int[n];
     //初始化顶部
     for(int i=0;i<n;i++){
         dp[i] = 1;
     }
     //遍历每一个格子
     for(int i=1;i<m;i++){
         for(int j=1;j<n;j++){
           //上面加左面的路径数
             dp[j] = dp[j-1]+dp[j];
         }
     }
     
     return dp[n-1];
    }

    public static void main(String[] args) {
        UniquePaths paths = new UniquePaths();
        int uniquePaths = paths.uniquePaths(1, 2);
        System.out.println(uniquePaths);
    }
}
